package class5;

import common.TreeNode;
import common.TreeNodeUtils;

/**
 * 是否为满二叉树
 */
public class Code16_IsFullTree {
    public static void main(String[] args) {
        TreeNode treeNode = TreeNodeUtils.getTreeNode();
        boolean full = isFull(treeNode);
        System.out.println("full = " + full);

    }

    public static boolean isFull(TreeNode treeNode) {
        Info info = process(treeNode);
        return info.nodes == (1 << info.high) - 1;
    }

    public static Info process(TreeNode treeNode) {
        if (treeNode == null) {
            return new Info(0, 0);
        }
        Info l = process(treeNode.left);
        Info r = process(treeNode.right);
        int high = Math.max(l.high, r.high) + 1;
        int nodes = l.nodes + r.nodes + 1;
        return new Info(high, nodes);
    }


    public static class Info {
        public int high;
        public int nodes;

        public Info(int high, int nodes) {
            this.high = high;
            this.nodes = nodes;
        }
    }


}
